class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        res = 0
        for i in range(m):
            for j in range(n):
                if self.getSum(i) + self.getSum(j) <= k:
                    res += 1
                # elif m == 1 or n == 1:
                #     return res
                # 1,100,10 29 x 应该 64
        return res

    def getSum(self, x):
        sums = 0
        while x != 0:
            sums += x % 10
            x = x // 10
        return sums
'''
不行，有些格子铁过不去！但是思路是比那里所有的情况
用例设置了阻碍，测试过不去
得到25 但是预期是15， 多了？？？
走到(4,0)不能再往下走了，(4,0)以后的点都访问不到了，没办法直接跳到(10,0)继续走的
机器人不能跳步！！！！
深度优先搜索： 可以理解为暴力法模拟机器人在矩阵中的所有路径。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝： 在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，称之为 可行性剪枝 。

'''
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def dfs(i, j, si, sj):
            # 终止条件： 当 ① 行列索引越界 或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过 时，返回 00 ，代表不计入可达解。
            # TypeError: unsupported operand type(s) for |: 'int' and 'tuple' 不能用|需要用or
            if i >= m or j >= n or k < si + sj or (i, j) in visited: return 0
            # 标记当前单元格 ：将索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。必须，否则有可能遍历的值大于真实值。
            visited.add((i,j))
            # 搜索下一单元格： 计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。
            # 回溯返回值： 返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。
            return 1 + dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj) + \
            dfs(i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8)
        visited = set()
        # 起点！
        return dfs(0,0,0,0)

print(Solution().movingCount(16,8,4))
# print(Solution().movingCount(1,100,10))
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        def dfs(i,j,sumi,sumj):
            # 结束条件，到最后一行就结束了
            if i >= m or j >= n or sumi + sumj > k or (i,j) in visited: return 0
            # 记录访问的历史记录
            visited.add((i,j))
            # 判断结尾是否是0，如果是，-8，不是 +1
            return 1 + dfs(i+1,j,sumi + 1 if (i+1)%10 else sumi -8,sumj) + dfs(i,j+1,sumi,sumj +1 if (j+1)%10 else sumj-8)
        visited = set()
        return dfs(0,0,0,0)